package org.example;

import java.util.Arrays;

/*斐波那契数列*/
public class Fibonacci {
    /* 暴力递归：时间复杂度为O(2^n),递归树->自顶向下 */
    // 观察递归树，可以很明显地发现算法低效的原因：存在大量重复计算，比如f(18)被计算了两次，多算一遍会耗费大量的时间。
    // 更何况还不止f(18)这一个节点被重复计算，所以这个算法及其低效。
    int fib(int N) {
        if (N == 0) {
            return 0;
        }
        if (N == 1 || N == 2) {
            return 1;
        }
        return fib(N - 1) + fib(N - 2);
    }

    /*带备忘录的递归解法:时间复杂度为O(N),递归树->自顶向下*/
    /*既然耗时的原因是重复计算，那么我们可以造一个“备忘录”，每次算出某个子问题的答案后别急着返回，先将其记到“备忘录”里再返回*/
    /*一般使用一个数组充当“备忘录”，当然你也可以使用哈希表（字典），思想都是一样的*/
    int fib1(int N){
        if (N == 0){
            return 0;
        }
        // 将备忘录全初始化为0
        int[] memo = new int[N + 1];
        Arrays.fill(memo, 0);
        // 进行带备忘录的递归
        return helper(memo, N);
    }

    int helper(int[] memo, int n){
        // base case
        if (n == 1 || n == 2) {
            return 1;
        }
        // 已经计算过
        if (memo[n] != 0){
            return memo[n];
        }
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }

    /* dp数组的迭代解法：O(N)，自底向上 */
    // 利用dp table
    int fib2(int N){
        if (N == 0){
            return 0;
        }
        if (N == 1 || N == 2){
            return 1;
        }
        int[] dp = new int[N + 1];
        Arrays.fill(dp, 0);
        // base case
        dp[1] = dp[2] = 1;
        for(int i = 3; i <= N; i++){
            dp[i] = dp[i-1] + dp[i - 2];
        }
        return dp[N];
    }

}
